The use of computer simulation for designing and verifying the logical operation of an electronic circuit design is well known. In the design of complex high-speed circuit networks, simulation analysis is required both to determine whether a performance objective is achieved, and to guide processes which attempt to meet that objective. Various techniques exist for finding the performance of part or all of a circuit network. However, these techniques generally must begin from scratch whenever any modification to the network design is made which might affect performance. Since many such modifications and adjustments are typically made to a design, and since the time required to compute the performance of even a small portion of a circuit network can be significant, a designer is typically forced to update design analysis at infrequent intervals. This means that many design decisions are made, either by the designer or by an automatic design optimization program, based on old information (such as changes to correct performance problems which may have already been corrected).
By way of specific example, the field of non-incremental static timing analysis is well developed. Existing methods generally start with arrival times at primary inputs, and propagate these arrival times through the logic network, adding the delays of the circuits and wires traversed during this propagation, to obtain arrival times at different points (or nodes) in the logic network. In a similar manner, required arrival times (i.e., required times) at primary outputs of the design are propagated backward through the logic network, subtracting the delays of the circuits and wires traversed during the propagation, to obtain required times at each point in the logic network. The difference between the required time and the arrival time at any point is called the "slack" at that point, which determines whether or not the signal at that point satisfies its timing requirements.
As a complication, certain signals are not propagated to primary outputs, but rather, are latched into storage elements. In such a case, proper function of the logic network requires a particular relationship between the arrival times of the signal controlling the latching of the data (the clock) and the data signal being latched. These are called timing test points, and their required relationship is the "test" between those points. The required time of a signal involved in such a test can be obtained from the arrival time of the other signal involved in the test.
The propagated arrival and required times may be single numbers, ranges of values, statistical distributions, sets of random samples calculated based on expected delay distributions and correlations, or a parametric equation representing the arrival/required times as a function of some design variable(s). Delays along the paths may be simply added or subtracted, or statistical or symbolic addition/subtraction may be utilized. Since paths within a logic network can diverge (i.e., fan-out) and converge (i.e., fan-in), the timing analysis process must also have a way of combining the arrival or required times propagated to a point. This is typically done by taking the maximum or minimum value, but may also involve maintaining several separate values at each point. The tests performed at storage elements may also be simple value comparisons, or may involve taking statistical or symbolic differences.
If the logic network may operate in different modes with different timing requirements or different paths being enabled (e.g., early mode and late mode), several separate timing analyses may be required to verify that a particular design meets its timing requirements. These may occur in parallel, or may be done in separate invocations of the timing analysis tool.
The propagation of arrival and required times may be accomplished in several different ways. One approach is to "levelize" the design, which means to determine an ordering of network elements such that no element precedes any other element that feeds it. By computing the arrival times in such a levelized order, all values for the computation of a single time at point X (i.e., the values of the points feeding X) will already have been computed by the time the value for point X is to be computed. Required times are computed by traversing the levelized list in the reverse order.
Another approach is to use recursive subroutine calls. Since the arrival time at any point X depends on the points feeding point X and the delays from those points, a recursive call can be made to obtain an arrival time for each of these points, causing the arrival times at all points within the cone of logic feeding point X to be computed. To avoid tracing all paths through the cone (which may grow exponentially with the size of a design), once a value for a point is computed it is saved, and when a call is made to request a value at that point, the saved value is returned.
Various methods exist in the art for updating timing analysis values. One approach is presented by Dunlop et al. in U.S. Pat. No. 4,827,428 entitled: "Transistor Sizing System for Integrated Circuits." This patent describes a method/system for improving the design of an integrated circuit by interactively analyzing the circuit and improving it with each iteration until a preselected constraint is met. Using a convex function model, with each iteration a static timing analysis of the circuit is completed to identify the output that most grievously violates the specified constraint. With that output selected, an analysis of the path's timing structure identifies the active element in that path whose change in size would yield the largest improvement in performance. The size of that active element is adjusted accordingly and the iteration is repeated. No description is provided, however, as to how the timing recalculation is to proceed.
Another approach to timing analysis is presented by Drumm et al. in U.S. Pat. No. 5,003,487 entitled: "Method and Apparatus for Performing Timing Correction Transformations on a Technology-Independent Logic Model During Logic Synthesis." This approach utilizes a depth first propagation of timing changes caused by a modification (or modifications) to the circuit network, until no further timing change occurs. Because a depth first search may traverse the same sub-paths many times, the approach is much more computationally expensive than truly needed. Further, because the application or user calling for timing analysis is provided the ability to control when recalculation is performed, recalculation may occur too often, causing excessive recomputation, or may not be conducted when appropriate, causing invalid answers to be given by the timing analyzer. Therefore, an application writer must be thoroughly familiar with this recalculation method in order to avoid the potential problems.
A need continues to exist in the art of designing complex, high-speed circuit networks for an efficient technique for updating timing analysis results in response to a partial (or incremental) modification to the network being timed. The invention described herein addresses this need. Additionally, the concepts provided can be used for incremental recalculation of any value which is propagated forward (or backward) through a logic network (or any other directed acyclic graph) such that the value at a point in the graph depends only on the values of the points feeding (or fed by) it.